package com.tgy.tree01;

import com.tgy.util.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/2/20 10:05 AM
 */
public abstract class BinaryTree<E> implements BinaryTreeInfo {

    protected int size;

    protected Node<E> root;

    protected static class Node<E>{

        E element;

        Node<E> left;
        Node<E> right;

        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {

            return left == null && right == null;
        }

        public boolean isLeft() {

            return parent != null && this.equals(parent.left);
        }

        public boolean isRight() {

            return parent != null && this.equals(parent.right);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Node)) return false;

            Node<?> node = (Node<?>) o;

            return element != null ? element.equals(node.element) : node.element == null;
        }

        @Override
        public int hashCode() {
            return element != null ? element.hashCode() : 0;
        }

        public int degree() {

            int degree = 0;

            if (left != null) {

                degree++;
            }

            if (right != null) {

                degree++;
            }

            return degree;
        }
    }

    public static abstract class Visit<E>{

        private boolean stop;

        public boolean isStop() {
            return stop;
        }

        public void setStop(boolean stop) {
            this.stop = stop;
        }

        public abstract  boolean visit(E element);
    }

    public BinaryTree() {


    }


    public boolean isEmpty() {

        return size == 0;
    }

    public abstract void add(E e);

    public abstract E remove(E e);

    /**
     * who is the root node
     */
    public Object root(){

        return root;
    }
    /**
     * how to get the left child of the node
     */
    public Object left(Object node) {


        return ((Node<E>)node).left;
    }
    /**
     * how to get the right child of the node
     */
    public Object right(Object node) {

        return ((Node<E>)node).right;
    }
    /**
     * how to print the node
     */
    public Object string(Object node) {

        return ((Node<E>)node).element;
    }


    /**
     * 层序遍历
     * @param visit
     */
    public void levelTraversal(Visit<E> visit) {


        if (root == null || visit == null) {

            return;
        }


        Queue<Node<E>> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {

            Node<E> node = queue.poll();

            if (node.left != null) {

                queue.offer(node.left);
            }

            if (node.right != null) {

                queue.offer(node.right);
            }

            if (visit.visit(node.element)) {

                return;
            }
        }
    }

    /**
     * 前序遍历
     * @param visit
     */
    public void preorderTraversal(Visit visit) {

        if (root == null || visit == null) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        Node<E> node = root;
        while (true) {

            while (node != null) {

                visit.visit(node.element);
                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {

                return;
            }

            node = stack.pop().right;
        }

    }

    public void preorderTraversal01(Visit<E> visit) {

        if (root == null || visit == null) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()) {

            Node<E> node = stack.pop();

            if (node.right != null) {

                stack.push(node.right);
            }

            if (node.left != null) {

                stack.push(node.left);
            }

            if (visit.visit(node.element)) {

                return;
            }
        }
    }

    public void inorderTraversal(Visit<E> visit) {

        if (root == null || visit == null) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        Node<E> node = root;
        while (true) {

            while (node != null) {

                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {

                return;
            }

            node = stack.pop();

            if (visit.visit(node.element)) {

                return;
            }

            node = node.right;
        }
    }

    public void postorderTraversal(Visit<E> visit) {

        if (root == null || visit == null) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        Node<E> visitNode = null;
        stack.push(root);

        while (!stack.isEmpty()) {

            Node<E> node = stack.peek();

            if (node.isLeaf() || (visitNode != null && visitNode.parent == node)) {

                visitNode = stack.pop();
                if (visit.visit(node.element)) {

                    return;
                }
                continue;
            }

            if (node.right != null) {

                stack.push(node.right);
            }

            if (node.left != null) {

                stack.push(node.left);
            }
        }

    }

}
